{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Number of Texts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #math #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #数学 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countTexts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计打字方案数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>Alice 在给 Bob 用手机打字。数字到字母的 <strong>对应</strong>&nbsp;如下图所示。</p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/03/15/1200px-telephone-keypad2svg.png\" style=\"width: 200px; height: 162px;\"></p>\n",
    "\n",
    "<p>为了 <strong>打出</strong>&nbsp;一个字母，Alice 需要 <strong>按</strong>&nbsp;对应字母 <code>i</code>&nbsp;次，<code>i</code>&nbsp;是该字母在这个按键上所处的位置。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，为了按出字母&nbsp;<code>'s'</code>&nbsp;，Alice 需要按&nbsp;<code>'7'</code>&nbsp;四次。类似的， Alice 需要按&nbsp;<code>'5'</code>&nbsp;两次得到字母&nbsp;&nbsp;<code>'k'</code>&nbsp;。</li>\n",
    "\t<li>注意，数字&nbsp;<code>'0'</code> 和&nbsp;<code>'1'</code>&nbsp;不映射到任何字母，所以&nbsp;Alice <strong>不</strong>&nbsp;使用它们。</li>\n",
    "</ul>\n",
    "\n",
    "<p>但是，由于传输的错误，Bob 没有收到 Alice 打字的字母信息，反而收到了 <strong>按键的字符串信息</strong>&nbsp;。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，Alice 发出的信息为&nbsp;<code>\"bob\"</code>&nbsp;，Bob 将收到字符串&nbsp;<code>\"2266622\"</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个字符串&nbsp;<code>pressedKeys</code>&nbsp;，表示 Bob 收到的字符串，请你返回 Alice <strong>总共可能发出多少种文字信息</strong>&nbsp;。</p>\n",
    "\n",
    "<p>由于答案可能很大，将它对&nbsp;<code>10<sup>9</sup> + 7</code>&nbsp;<strong>取余</strong> 后返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>pressedKeys = \"22233\"\n",
    "<b>输出：</b>8\n",
    "<strong>解释：</strong>\n",
    "Alice 可能发出的文字信息包括：\n",
    "\"aaadd\", \"abdd\", \"badd\", \"cdd\", \"aaae\", \"abe\", \"bae\" 和 \"ce\" 。\n",
    "由于总共有 8 种可能的信息，所以我们返回 8 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>pressedKeys = \"222222222222222222222222222222222222\"\n",
    "<b>输出：</b>82876089\n",
    "<strong>解释：</strong>\n",
    "总共有 2082876103 种 Alice 可能发出的文字信息。\n",
    "由于我们需要将答案对 10<sup>9</sup> + 7 取余，所以我们返回 2082876103 % (10<sup>9</sup> + 7) = 82876089 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= pressedKeys.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>pressedKeys</code> 只包含数字&nbsp;<code>'2'</code>&nbsp;到&nbsp;<code>'9'</code>&nbsp;。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-number-of-texts](https://leetcode.cn/problems/count-number-of-texts/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-number-of-texts](https://leetcode.cn/problems/count-number-of-texts/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"22233\"', '\"222222222222222222222222222222222222\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        a = b = c = d = 1\n",
    "        for index in range(1, len(pressedKeys)):\n",
    "            now = 0\n",
    "            if pressedKeys[index] == pressedKeys[index - 1]:\n",
    "                if index >= 2 and pressedKeys[index] == pressedKeys[index - 2]:\n",
    "                    if index >= 3 and pressedKeys[index] == pressedKeys[index - 3] and (pressedKeys[index] == '7' or pressedKeys[index] == '9'):\n",
    "                        now += a\n",
    "                        if now >= mod:\n",
    "                            now -= mod\n",
    "                    \n",
    "                    now += b\n",
    "                    if now >= mod:\n",
    "                        now -= mod\n",
    "                \n",
    "                now += c\n",
    "                if now >= mod:\n",
    "                    now -= mod\n",
    "            \n",
    "            now += d\n",
    "            if now >= mod:\n",
    "                now -= mod\n",
    "\n",
    "            a, b, c, d = b, c, d, now\n",
    "        \n",
    "        return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        d = {}\n",
    "        d4 = {}\n",
    "        d_l = [4,1,2]\n",
    "        d4_l = [1,1,2,4]\n",
    "        cur_i = 0\n",
    "        d[1]=1\n",
    "        d[2]=2\n",
    "        d[3]=4\n",
    "        d4[1]=1\n",
    "        d4[2]=2\n",
    "        d4[3]=4\n",
    "        len_list = []\n",
    "        for j in range(1,len(pressedKeys)):\n",
    "            if pressedKeys[j] != pressedKeys[cur_i]:\n",
    "                len_list.append(j-cur_i)\n",
    "                cur_i = j\n",
    "        len_list.append(len(pressedKeys)-cur_i)\n",
    "        max_len = max(len_list)\n",
    "        print(len_list)\n",
    "        for i in range(4,max_len+1):\n",
    "            d_l[i%3] = d_l[0]+d_l[1]+d_l[2]\n",
    "            d4_l[i%4] =d4_l[0] + d4_l[1] + d4_l[2] +d4_l[3]\n",
    "            if i in len_list:\n",
    "                d[i] = d_l[i%3]\n",
    "                d4[i] = d4_l[i%4]\n",
    "  \n",
    "        ret = 1\n",
    "        cur_i = 0\n",
    "        for j in range(1,len(pressedKeys)):\n",
    "            if pressedKeys[j] != pressedKeys[cur_i]:\n",
    "                if  pressedKeys[cur_i] in [ '7','9']:\n",
    "                    ret = ret * d4[j-cur_i]\n",
    "                else:\n",
    "                    ret = ret * d[j-cur_i]\n",
    "                ret = ret%(10**9 + 7)\n",
    "                cur_i = j\n",
    "        if  pressedKeys[cur_i] in [ '7','9']:\n",
    "            ret = ret * d4[len(pressedKeys)-cur_i]\n",
    "        else:\n",
    "            ret = ret * d[len(pressedKeys)-cur_i]\n",
    "        return ret%(10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        # 与解码方法题目类似，前缀可以有多种不同的可能，枚举所有的可能相加即可\n",
    "        MOD = 10**9+7\n",
    "        n = len(pressedKeys)\n",
    "        num_dict = {2:3,3:3,4:3,5:3,6:3,7:4,8:3,9:4}\n",
    "        dp = [0]*(n+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1,n+1):\n",
    "            cur = pressedKeys[i-1]\n",
    "            back_steps = num_dict[int(cur)]\n",
    "            dp[i] = dp[i-1]\n",
    "            for j in range(i-1, i-back_steps, -1):\n",
    "                if j<1 or pressedKeys[j-1]!=cur:\n",
    "                    break\n",
    "                dp[i] = (dp[i] + dp[j-1])%MOD\n",
    "        return dp[-1]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    线性DP\n",
    "    dp[i]表示前i个数字形成的子串，能形成的所有文字信息数量\n",
    "    假设pressKeys[i] = a，前面连续的m位也是a，那么诸如 aaa 这种\n",
    "    dp[2] = dp[1] + dp[0] + 1，也就是aaa可以分成 aa-a（dp[1]）、a-aa（dp[0]）之和，再加aaa一个整体\n",
    "    '''\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        cnt = {'2':3, '3':3, '4':3, '5':3, '6':3, '7':4, '8':3, '9':4}\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(pressedKeys)\n",
    "        '''\n",
    "        要多一位的原因是，为了兼容aaa整体作为一种方案的情况\n",
    "        dp[0] = 1也是为了兼容，比如dp[3] = dp[2] + dp[1] + dp[0]，这个dp[0]就相当于所有按钮整体都是一种组合\n",
    "        '''\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0] = 1\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            '''\n",
    "            如果前面存在连续字段，最远能到达哪里 j 对应dp数组的下标\n",
    "            '''\n",
    "            j = max(0, i - cnt[pressedKeys[i - 1]])\n",
    "            for k in range(i, j, -1):\n",
    "                '''\n",
    "                因为j最小是0，那么k最小就是1，还是可以对应dp的下标，对应元素组下标就要减一，如果存在连续相同字符，\n",
    "                每一种可能都累加一次前面连续字符结尾的组合数\n",
    "                '''\n",
    "                if pressedKeys[i - 1] != pressedKeys[k - 1]:\n",
    "                    break\n",
    "                '''\n",
    "                注意dp[i]是包括i的，所以k最小为1，那么累加的就需要看前面一位  （比较绕，仔细看看）\n",
    "                '''\n",
    "                dp[i] += dp[k - 1]\n",
    "            dp[i] %= mod\n",
    "        \n",
    "        return dp[-1] % mod\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        MOD = 10**9+7\n",
    "        n = len(pressedKeys)\n",
    "        num_dict = {2:3,3:3,4:3,5:3,6:3,7:4,8:3,9:4}\n",
    "        dp = [0]*(n+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1,n+1):\n",
    "            cur = pressedKeys[i-1]\n",
    "            back_steps = num_dict[int(cur)]\n",
    "            dp[i] = dp[i-1]\n",
    "            for j in range(i-1, i-back_steps, -1):\n",
    "                if j<1 or pressedKeys[j-1]!=cur:\n",
    "                    break\n",
    "                dp[i] = (dp[i] + dp[j-1])%MOD\n",
    "        return dp[-1]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        # 2 -> 1\n",
    "        # 22 -> 1 + 1\n",
    "        # 222 -> 2 + 1 + 1\n",
    "        # 2222 -> 4 + 2 + 1\n",
    "        def cal(s, x):\n",
    "            n = len(s)\n",
    "            f = [0] * (n + 1)\n",
    "            f[0] = 1\n",
    "            for i in range(1, n + 1):\n",
    "                for j in range(i - x, i, 1):\n",
    "                    f[i] = ((f[j] if j >= 0 else 0) + f[i]) % mod\n",
    "                    \n",
    "            # print(f'{f}')\n",
    "            \n",
    "            return f[-1]\n",
    "        \n",
    "        ks = pressedKeys\n",
    "        n = len(ks)\n",
    "        i, ans = 0, 1\n",
    "        while i < n:\n",
    "            j = i\n",
    "            while j < n and ks[j] == ks[i]:\n",
    "                j += 1\n",
    "            # print(f'{ks[i:j]}')\n",
    "            ans = ans * cal(ks[i:j], 4 if ks[i] == '9' or ks[i] == '7' else 3)\n",
    "            ans %= mod\n",
    "            i = j\n",
    "        return ans\n",
    "            \n",
    "                    \n",
    "                    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        cnt = {'2':3, '3':3, '4':3, '5':3, '6':3, '7':4, '8':3, '9':4}\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(pressedKeys)\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0] = 1\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            j = max(0, i - cnt[pressedKeys[i - 1]])\n",
    "            for k in range(i, j, -1):\n",
    "                if k and pressedKeys[i - 1] != pressedKeys[k - 1]:\n",
    "                    break\n",
    "                dp[i] += dp[k - 1]\n",
    "            dp[i] %= mod\n",
    "        \n",
    "        return dp[-1] % mod\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "                \n",
    "        MOD = 10**9 + 7\n",
    "        \n",
    "        n = len(pressedKeys)\n",
    "        dp = [1] * n    # 初始化\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            # pressedKeys[i] != pressedKeys[i-1]，则pressedKeys[i]无贡献\n",
    "            if pressedKeys[i] != pressedKeys[i-1]:\n",
    "                dp[i] = dp[i-1]    \n",
    "            # pressedKeys[i] = pressedKeys[i-1]\n",
    "            else:\n",
    "                if i < 2 or pressedKeys[i] != pressedKeys[i-2]:\n",
    "                    # pressedKeys[i] = pressedKeys[i-1] != pressedKeys[i-2]\n",
    "                    dp[i] = dp[i-1] + (dp[i-2] if i>=2 else 1)\n",
    "                else:   \n",
    "                    # pressedKeys[i] = pressedKeys[i-1] = pressedKeys[i-2]\n",
    "                    dp[i] = dp[i-1] + dp[i-2] + (dp[i-3] if i>=3 else 1)\n",
    "                    \n",
    "                    # 特别判断 '7' 和 '9'\n",
    "                    if (pressedKeys[i] == '9' or pressedKeys[i] == '7') and i >= 3 and pressedKeys[i] == pressedKeys[i-3]:\n",
    "                        # pressedKeys[i] = pressedKeys[i-1] = pressedKeys[i-2] = pressedKeys[i-3]\n",
    "                        dp[i] += (dp[i-4] if i>=4 else 1)\n",
    "\n",
    "            dp[i] %= MOD\n",
    "        \n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "mod = 10**9 + 7\n",
    "\n",
    "st = \"abc,def,ghi,jkl,mno,pqrs,tuv,wxyz\"\n",
    "lst = st.split(\",\")\n",
    "dct = dict()\n",
    "for i, word in enumerate(lst):\n",
    "    i += 2\n",
    "    for j, w in enumerate(word):\n",
    "        dct[str(i)*(j+1)] = 1\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        n = len(pressedKeys)\n",
    "        dp = [0]*(n+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(n):\n",
    "            for j in range(max(i-4, 0), i+1):\n",
    "                if pressedKeys[j:i+1] in dct:\n",
    "                    dp[i+1] += dp[j]\n",
    "                    dp[i+1] %= mod\n",
    "        return dp[-1] % mod\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        cnt=1\n",
    "        i=0\n",
    "        mod=10**9+7\n",
    "        m=len(pressedKeys)\n",
    "        while i<m:\n",
    "            t=pressedKeys[i]\n",
    "            tmp=pressedKeys[i]\n",
    "            while i+1<m and pressedKeys[i+1]==t:\n",
    "                i=i+1\n",
    "                tmp+=t\n",
    "            n=len(tmp)\n",
    "\n",
    "            dp=[0]*(n+1)\n",
    "       \n",
    "            if t==\"7\" or t==\"9\":\n",
    "                k=4\n",
    "            else:\n",
    "                k=3\n",
    "            dp[0]=1\n",
    "            for j in range(1,n+1):\n",
    "                for a in range(1,k+1):\n",
    "                    if j-a>=0:\n",
    "                        dp[j]=(dp[j]+dp[j-a])%mod\n",
    "                    else:\n",
    "                        break\n",
    "           # print(tmp,dp[-1],k)\n",
    "            cnt=(cnt*dp[-1])%mod\n",
    "            i=i+1\n",
    "        return cnt\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        max4Len = max3Len = 0\n",
    "        for c, grp in groupby(pressedKeys):\n",
    "            l = sum(1 for _ in grp)\n",
    "            if c in '79':\n",
    "                max4Len = max(max4Len, l)\n",
    "            else:\n",
    "                max3Len = max(max3Len, l)\n",
    "        P = 10**9+7\n",
    "        threes = fours = []\n",
    "        if max3Len:\n",
    "            threes = [0]*(max3Len + 1)\n",
    "            threes[1:4] = [1, 2, 4]\n",
    "            _sum = sum(threes[:3])\n",
    "            last = threes[3]\n",
    "            for n in range(4, max3Len+1):\n",
    "                _sum = (_sum + last - threes[n-4]) % P\n",
    "                threes[n] = last = _sum\n",
    "                \n",
    "        if max4Len:\n",
    "            fours = [0]*(max4Len + 1)\n",
    "            fours[1:5] = [1, 2, 4, 8]\n",
    "            _sum = sum(fours[:4])\n",
    "            last = fours[4]\n",
    "            for n in range(5, max4Len+1):\n",
    "                _sum = (_sum + last - fours[n-5]) % P\n",
    "                fours[n] = last = _sum\n",
    "        #print(max3Len, max4Len)        \n",
    "        # print(threes, fours)\n",
    "        result = 1\n",
    "        for c, grp in groupby(pressedKeys):\n",
    "            l = sum(1 for _ in grp)\n",
    "            if c in '79':\n",
    "                result = result*fours[l] %P\n",
    "            else:\n",
    "                result = result*threes[l]%P\n",
    "        return result\n",
    "        r[n] = r[n-3] + r[n-2] + r[n-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 **9 + 7\n",
    "MAPPING = {'7': 4, '9': 4, '2': 3, '3': 3, '4': 3, '5': 3, '6': 3, '8': 3}\n",
    "class Solution:   \n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        n = len(pressedKeys)\n",
    "        f = [1] + [0] * n\n",
    "        for i,x in enumerate(pressedKeys):\n",
    "            for j in range(i, i-MAPPING[x], -1):\n",
    "                if j<0 or pressedKeys[j] != x:\n",
    "                    break\n",
    "                f[i+1] = (f[j] + f[i+1])%MOD\n",
    "        return f[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        mod = int(1e9+7)\n",
    "        n = len(pressedKeys)\n",
    "        dp = [0 for i in range(n+1)]\n",
    "        dp[0]=dp[1] =1\n",
    "        letters = [0,0,3,3,3,3,3,4,3,4]\n",
    "        for i in range(2,n+1):\n",
    "            c = pressedKeys[i-1]\n",
    "            j = i\n",
    "            while j>=1 and i-j+1 <= letters[ord(c)-ord('0')] and pressedKeys[j-1]==c:\n",
    "                dp[i] += dp[j-1]\n",
    "                dp[i] %= mod\n",
    "                j-=1\n",
    "        print(dp)\n",
    "        return dp[n] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        m = 7+10**9\n",
    "        dp3 = [0, 1, 2, 4]\n",
    "        dp4 = [0, 1, 2, 4, 8]\n",
    "        # dp3 = [1, 1, 2, 4]\n",
    "        # dp4 = [1, 1, 2, 4]\n",
    "        n = len(pressedKeys)\n",
    "        for i in range(4, n+1):\n",
    "            dp3.append((dp3[i-1]+dp3[i-2]+dp3[i-3])%m)\n",
    "        for i in range(5, n+1):\n",
    "            dp4.append((dp4[i-1]+dp4[i-2]+dp4[i-3]+dp4[i-4])%m)\n",
    "        cnt=1\n",
    "        res=1\n",
    "        for i in range(1, n):\n",
    "            if pressedKeys[i-1]==pressedKeys[i]:\n",
    "                cnt+=1\n",
    "            else:\n",
    "                if pressedKeys[i-1] in '79':\n",
    "                    res*=dp4[cnt]\n",
    "                else:\n",
    "                    res*=dp3[cnt]\n",
    "                res%=m\n",
    "                cnt=1\n",
    "        if pressedKeys[n-1] in '79':\n",
    "            res*=dp4[cnt]\n",
    "        else:\n",
    "            res*=dp3[cnt]\n",
    "        res%=m\n",
    "        return int(res)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "M = 10**9+7\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        N = len(pressedKeys)\n",
    "        if(N == 1):\n",
    "            return 1\n",
    "        dp1 = [0]*(N+1)\n",
    "        dp1[0], dp1[1], dp1[2] = 1, 1, 2\n",
    "        for i in range(3,N+1):\n",
    "            dp1[i] = (dp1[i-1] + dp1[i-2] + dp1[i-3])%M\n",
    "\n",
    "        dp2 = [0]*(N+1)\n",
    "        dp2[0], dp2[1], dp2[2], dp2[3] = 1, 1, 2, 4\n",
    "        for i in range(4,N+1):\n",
    "            dp2[i] = (dp2[i-1] + dp2[i-2] + dp2[i-3] +dp2[i-4])%M\n",
    "        cnt = 0\n",
    "        pre = None\n",
    "        result = 1\n",
    "        for c in pressedKeys:\n",
    "            if(c != pre):\n",
    "                if(pre != None):\n",
    "                    if(pre in ('7', '9')):\n",
    "                        result = result * dp2[cnt] % M\n",
    "                    else:\n",
    "                        result = result * dp1[cnt] % M\n",
    "                pre = c \n",
    "                cnt = 1\n",
    "            else:\n",
    "                cnt += 1\n",
    "        if(pre in ('7', '9')):\n",
    "            result = result * dp2[cnt] % M\n",
    "        else:\n",
    "            result = result * dp1[cnt] % M\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        m = 7+10**9\n",
    "        dp3 = [0, 1, 2, 4]\n",
    "        dp4 = [0, 1, 2, 4, 8]\n",
    "        # dp3 = [1, 1, 2, 4]\n",
    "        # dp4 = [1, 1, 2, 4]\n",
    "        n = len(pressedKeys)\n",
    "        for i in range(4, n+1):\n",
    "            dp3.append((dp3[i-1]+dp3[i-2]+dp3[i-3])%m)\n",
    "        for i in range(5, n+1):\n",
    "            dp4.append((dp4[i-1]+dp4[i-2]+dp4[i-3]+dp4[i-4])%m)\n",
    "        cnt=1\n",
    "        res=1\n",
    "        for i in range(1, n):\n",
    "            if pressedKeys[i-1]==pressedKeys[i]:\n",
    "                cnt+=1\n",
    "            else:\n",
    "                if pressedKeys[i-1] in '79':\n",
    "                    res*=dp4[cnt]\n",
    "                else:\n",
    "                    res*=dp3[cnt]\n",
    "                # res%=m\n",
    "                cnt=1\n",
    "        if pressedKeys[n-1] in '79':\n",
    "            res*=dp4[cnt]\n",
    "        else:\n",
    "            res*=dp3[cnt]\n",
    "        res%=m\n",
    "        return int(res)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        m = 7+10 ** 9\n",
    "        dp3 = [0, 1, 2, 4]\n",
    "        dp4 = [0, 1, 2, 4, 8]\n",
    "        # dp3 = [1, 1, 2, 4]\n",
    "        # dp4 = [1, 1, 2, 4]\n",
    "        n = len(pressedKeys)\n",
    "        for i in range(4, n+1):\n",
    "            dp3.append((dp3[i-1]+dp3[i-2]+dp3[i-3])%m)\n",
    "        for i in range(5, n+1):\n",
    "            dp4.append((dp4[i-1]+dp4[i-2]+dp4[i-3]+dp4[i-4])%m)\n",
    "        cnt=1\n",
    "        res=1\n",
    "        for i in range(1, n):\n",
    "            if pressedKeys[i-1]==pressedKeys[i]:\n",
    "                cnt+=1\n",
    "            else:\n",
    "                if pressedKeys[i-1] in '79':\n",
    "                    res*=dp4[cnt]\n",
    "                else:\n",
    "                    res*=dp3[cnt]\n",
    "                res%=m\n",
    "                cnt=1\n",
    "        if pressedKeys[n-1] in '79':\n",
    "            res*=dp4[cnt]\n",
    "        else:\n",
    "            res*=dp3[cnt]\n",
    "        res%=m\n",
    "        return int(res)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "M = 10**9+7\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        N = len(pressedKeys)\n",
    "        if(N == 1):\n",
    "            return 1\n",
    "        dp1 = [0]*(N+1)\n",
    "        dp1[0], dp1[1], dp1[2] = 1, 1, 2\n",
    "        for i in range(3,N+1):\n",
    "            dp1[i] = (dp1[i-1] + dp1[i-2] + dp1[i-3])%M\n",
    "\n",
    "        dp2 = [0]*(N+1)\n",
    "        dp2[0], dp2[1], dp2[2], dp2[3] = 1, 1, 2, 4\n",
    "        for i in range(4,N+1):\n",
    "            dp2[i] = (dp2[i-1] + dp2[i-2] + dp2[i-3] +dp2[i-4])%M\n",
    "        cnt = 0\n",
    "        pre = None\n",
    "        result = 1\n",
    "        for c in pressedKeys:\n",
    "            if(c != pre):\n",
    "                if(pre != None):\n",
    "                    if(pre in ('7', '9')):\n",
    "                        result = result * dp2[cnt] % M\n",
    "                    else:\n",
    "                        result = result * dp1[cnt] % M\n",
    "                pre = c \n",
    "                cnt = 1\n",
    "            else:\n",
    "                cnt += 1\n",
    "        if(pre in ('7', '9')):\n",
    "            result = result * dp2[cnt] % M\n",
    "        else:\n",
    "            result = result * dp1[cnt] % M\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10 ** 9 + 7\n",
    "dp3 = [0] * (10 ** 5 + 1)\n",
    "dp4 = [0] * (10 ** 5 + 1)\n",
    "dp3[0] = 1\n",
    "dp4[0] = 1\n",
    "for i in range(1, 10 ** 5 + 1):\n",
    "    dp3[i] = dp3[i-1] + dp3[i-2] + dp3[i-3]\n",
    "    dp4[i] = dp4[i-1] + dp4[i-2] + dp4[i-3] + dp4[i-4]\n",
    "    dp3[i] %= mod\n",
    "    dp4[i] %= mod\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, s: str) -> int:\n",
    "        char, cnt = '', 0\n",
    "        ans = 1\n",
    "        for c in s:\n",
    "            if char == c:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                if char in '79': ans *= dp4[cnt]\n",
    "                else: ans *= dp3[cnt]\n",
    "                ans %= mod\n",
    "                char = c\n",
    "                cnt = 1\n",
    "        \n",
    "        if char in '79': ans *= dp4[cnt]\n",
    "        else: ans *= dp3[cnt]\n",
    "        ans %= mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = int(1e9 + 7)\n",
    "\n",
    "# 3个头\n",
    "f = [1, 1, 2, 4]\n",
    "\n",
    "# 4个头\n",
    "g = [1, 1, 2, 4]\n",
    "\n",
    "for i in range(4, int(1e5) + 1):\n",
    "    f.append((f[-1] + f[-2] + f[-3]) % mod)\n",
    "    g.append((g[-1] + g[-2] + g[-3] + g[-4]) % mod)\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "\n",
    "        alph = {\n",
    "            2:3,\n",
    "            3:3,\n",
    "            4:3,\n",
    "            5:3,\n",
    "            6:3,\n",
    "            7:4,\n",
    "            8:3,\n",
    "            9:4\n",
    "        }\n",
    "\n",
    "        res = 1\n",
    "\n",
    "        i = 0\n",
    "        while i < len(pressedKeys):\n",
    "            start = i\n",
    "\n",
    "            while i < len(pressedKeys) and pressedKeys[i] == pressedKeys[start]:\n",
    "                i += 1\n",
    "            \n",
    "            size = i - start\n",
    "\n",
    "            # res *= dp(alph[int(pressedKeys[start])], size)\n",
    "            res *= f[size] if alph[int(pressedKeys[start])] == 3 else g[size]\n",
    "            res %= mod\n",
    "        \n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        n = len(pressedKeys)\n",
    "        dp3 = [0] * max(3, (n + 1))\n",
    "        dp4 = [0] * max(4, (n + 1))\n",
    "        M = 10 ** 9 + 7\n",
    "        dp3[0], dp3[1], dp3[2] = 1, 1, 2\n",
    "        for i in range(3, n + 1):\n",
    "            dp3[i] = (dp3[i - 1] + dp3[i - 2] + dp3[i - 3]) % M\n",
    "        dp4[0], dp4[1], dp4[2], dp4[3] = 1, 1, 2, 4\n",
    "        for i in range(4, n + 1):\n",
    "            dp4[i] = (dp4[i - 1] + dp4[i - 2] + dp4[i - 3] + dp4[i - 4]) % M\n",
    "\n",
    "        pre = pressedKeys[0]\n",
    "        cnt = 1\n",
    "        ret = 1\n",
    "        pressedKeys += '1'\n",
    "        for x in pressedKeys[1:]:\n",
    "            if pre == x:\n",
    "                cnt += 1\n",
    "            else:           \n",
    "                k = dp3[cnt] if pre != '9' and pre != '7' else dp4[cnt]\n",
    "                ret = ret * k % M\n",
    "                cnt, pre = 1, x\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        digit_to_map = {\"2\":3,\"3\":3, \"4\":3,\"5\":3,\"6\":3,\"7\":4,\"8\":3,\"9\":4}\n",
    "\n",
    "   \n",
    "        key_len = len(pressedKeys)\n",
    "            \n",
    "        dp3 = [1]*max(key_len,4)\n",
    "        dp4 = [1]*max(key_len,4)\n",
    "        for i in range(1, 3):\n",
    "            dp3[i] = dp3[i-1]*2\n",
    "            dp4[i] = dp4[i-1]*2\n",
    "        dp4[3] = 8\n",
    "        dp3_old = 7\n",
    "        dp4_old = 15\n",
    "        for i in range(3, key_len):\n",
    "            dp3[i] = dp3_old\n",
    "            dp3_old =(2*dp3_old-dp3[i-3])%(10**9+7)\n",
    "            \n",
    "        for i in range(4, key_len):\n",
    "            dp4[i] = dp4_old\n",
    "            dp4_old = (2*dp4_old-dp4[i-4])%(10**9+7)\n",
    "        left = right = 0\n",
    "        ans = 1\n",
    "        while right< key_len:\n",
    "            if pressedKeys[right]!= pressedKeys[left]:\n",
    "                v = pressedKeys[left]\n",
    "                dis = right-left\n",
    "                if digit_to_map[v] ==3:\n",
    "                    ans *= dp3[dis-1]\n",
    "\n",
    "                else:\n",
    "                    ans *= dp4[dis-1]\n",
    "                left = right\n",
    "            right+=1\n",
    "        if left != key_len-1:\n",
    "            v = pressedKeys[left]\n",
    "            dis = right-left\n",
    "            if digit_to_map[v] ==3:\n",
    "                ans *= dp3[dis-1]\n",
    "            else:\n",
    "                ans *= dp4[dis-1]\n",
    "        return ans %(10**9+7)\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 2，3，4，5，6，8\n",
    "# 7，9\n",
    "MX = 10**5+1\n",
    "MOD = 10**9+7\n",
    "f = [1, 1, 2, 4]\n",
    "g = [1, 1, 2, 4]\n",
    "for i in range(4,MX):  # 预处理所有长度的结果\n",
    "    f.append((f[i-1] + f[i-2] + f[i-3]) % MOD)\n",
    "    g.append((g[i-1] + g[i-2] + g[i-3] + g[i-4]) % MOD)\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        cnt = 1\n",
    "        ans = 1\n",
    "        mod = 10**9+7\n",
    "        n = len(pressedKeys)\n",
    "        for i in range(1,n):\n",
    "            if pressedKeys[i] == pressedKeys[i-1]:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                if pressedKeys[i-1] in '79':\n",
    "                    ans *= g[cnt]\n",
    "                else:\n",
    "                    ans *= f[cnt]\n",
    "                ans %= mod\n",
    "                cnt = 1\n",
    "        if pressedKeys[-1] in '79':\n",
    "            ans *= g[cnt]\n",
    "        else:\n",
    "            ans *= f[cnt]\n",
    "        return ans%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "f = [1, 1, 2, 4]\n",
    "g = [1, 1, 2, 4]\n",
    "for _ in range(10 ** 5 - 3):  # 预处理所有长度的结果\n",
    "    f.append((f[-1] + f[-2] + f[-3]) % MOD)\n",
    "    g.append((g[-1] + g[-2] + g[-3] + g[-4]) % MOD)\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        ans = 1\n",
    "        for ch, s in groupby(pressedKeys):\n",
    "            m = len(list(s))\n",
    "            ans = ans * (g[m] if ch in \"79\" else f[m]) % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod=10**9+7\n",
    "dp3=[1,1,2,4]\n",
    "dp4=[1,1,2,4]\n",
    "for _ in range(10**5):\n",
    "    dp3.append((dp3[-1]+dp3[-2]+dp3[-3])%mod)\n",
    "    dp4.append((dp4[-1]+dp4[-2]+dp4[-3]+dp4[-4])%mod)\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        i,j=0,0\n",
    "        n=len(pressedKeys)\n",
    "        #d=collections.defaultdict(list)\n",
    "        ans=1\n",
    "        #l=0\n",
    "        while j<n and i<n: \n",
    "            while j<n and pressedKeys[i]==pressedKeys[j]:\n",
    "                j+=1\n",
    "            #l=max(l,j-i)\n",
    "            #d[pressedKeys[i]].append(j-i)\n",
    "            if pressedKeys[i] in [\"7\",\"9\"]:\n",
    "                print(i,j,j-i,pressedKeys[i],4)\n",
    "                ans*=dp4[j-i]\n",
    "                ans%=mod\n",
    "            else:\n",
    "                print(i,j,j-i,pressedKeys[i],3)\n",
    "                ans*=dp3[j-i]\n",
    "                ans%=mod\n",
    "            i=j\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        m = 7+10 ** 9\n",
    "        # dp3 = [0, 1, 2, 4]\n",
    "        # dp4 = [0, 1, 2, 4, 8]\n",
    "        dp3 = [1, 1, 2, 4]\n",
    "        dp4 = [1, 1, 2, 4]\n",
    "        n = len(pressedKeys)\n",
    "        for i in range(4, n+1):\n",
    "            dp3.append((dp3[i-1]+dp3[i-2]+dp3[i-3])%m)\n",
    "            dp4.append((dp4[i-1]+dp4[i-2]+dp4[i-3]+dp4[i-4])%m)\n",
    "        cnt=1\n",
    "        res=1\n",
    "        for i in range(1, n):\n",
    "            if pressedKeys[i-1]==pressedKeys[i]:\n",
    "                cnt+=1\n",
    "            else:\n",
    "                if pressedKeys[i-1] in '79':\n",
    "                    res*=dp4[cnt]\n",
    "                else:\n",
    "                    res*=dp3[cnt]\n",
    "                res%=m\n",
    "                cnt=1\n",
    "        if pressedKeys[n-1] in '79':\n",
    "            res*=dp4[cnt]\n",
    "        else:\n",
    "            res*=dp3[cnt]\n",
    "        res%=m\n",
    "        return int(res)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "f = [1, 1, 2, 4]\n",
    "g = [1, 1, 2, 4]\n",
    "for _ in range(10 ** 5 - 3):  # 预处理所有长度的结果\n",
    "    f.append((f[-1] + f[-2] + f[-3]) % MOD)\n",
    "    g.append((g[-1] + g[-2] + g[-3] + g[-4]) % MOD)\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        ans = 1\n",
    "        for ch, s in groupby(pressedKeys):\n",
    "            m = len(list(s))\n",
    "            ans = ans * (g[m] if ch in \"79\" else f[m]) % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "f = [1, 1, 2, 4]\n",
    "g = [1, 1, 2, 4]\n",
    "for _ in range(10 ** 5 - 3): # 预处理所有长度的结果\n",
    "    f.append((f[-1] + f[-2] + f[-3]) % MOD)\n",
    "    g.append((g[-1] + g[-2] + g[-3] + g[-4]) % MOD)\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "\n",
    "        ans = 1\n",
    "        for ch, s in groupby(pressedKeys):\n",
    "            m = len(list(s))\n",
    "            ans = ans * (g[m] if ch in \"79\" else f[m]) % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\r\n",
    "# @lc app=leetcode.cn id=2266 lang=python3\r\n",
    "#\r\n",
    "# [2266] 统计打字方案数\r\n",
    "#\r\n",
    "\r\n",
    "MOD = 10 ** 9 + 7\r\n",
    "f = [1, 1, 2, 4]\r\n",
    "g = [1, 1, 2, 4]\r\n",
    "for _ in range(10 ** 5 - 3):  # 预处理所有长度的结果\r\n",
    "    f.append((f[-1] + f[-2] + f[-3]) % MOD)\r\n",
    "    g.append((g[-1] + g[-2] + g[-3] + g[-4]) % MOD)\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def countTexts(self, pressedKeys: str) -> int:\r\n",
    "        ans = 1\r\n",
    "        for ch, s in groupby(pressedKeys):\r\n",
    "            m = len(list(s))\r\n",
    "            ans = ans * (g[m] if ch in \"79\" else f[m]) % MOD\r\n",
    "        return ans\r\n",
    "\r\n",
    "\r\n",
    "    \r\n",
    "print(Solution().countTexts(\"22233\"))\r\n",
    "# @lc code=end\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理\n",
    "# '234568'\n",
    "mod = 10**9+7\n",
    "f = [1,1,2,4]\n",
    "# '79'\n",
    "g = [1,1,2,4]\n",
    "MX = 10**5+1\n",
    "for i in range(4,MX):\n",
    "    f.append((f[i-1]+f[i-2]+f[i-3])%mod)\n",
    "    g.append((g[i-1]+g[i-2]+g[i-3]+g[i-4])%mod) \n",
    "# '79'\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        ans = 1\n",
    "        for ch,s in groupby(pressedKeys):\n",
    "            m = len(list(s))\n",
    "            if ch in '79':\n",
    "                ans *= g[m]\n",
    "            else:\n",
    "                ans *= f[m]\n",
    "        return ans%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "f = [1, 1, 2, 4]\n",
    "\n",
    "g = [1, 1, 2, 4]\n",
    "\n",
    "for _ in range(10 ** 5 - 3):  # 预处理所有长度的结果\n",
    "\n",
    "    f.append((f[-1] + f[-2] + f[-3]) % MOD)\n",
    "\n",
    "    g.append((g[-1] + g[-2] + g[-3] + g[-4]) % MOD)\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        ans = 1\n",
    "\n",
    "        for ch, s in groupby(pressedKeys):\n",
    "\n",
    "            m = len(list(s))\n",
    "\n",
    "            ans = ans * (g[m] if ch in \"79\" else f[m]) % MOD\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "f = [1, 1, 2, 4]\n",
    "g = [1, 1, 2, 4]\n",
    "for _ in range(10 ** 5 - 3):  # 预处理所有长度的结果\n",
    "    f.append((f[-1] + f[-2] + f[-3]) % MOD)\n",
    "    g.append((g[-1] + g[-2] + g[-3] + g[-4]) % MOD)\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        ans = 1\n",
    "        for ch, s in groupby(pressedKeys):\n",
    "            m = len(list(s))\n",
    "            ans = ans * (g[m] if ch in \"79\" else f[m]) % MOD\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 2，3，4，5，6，8\n",
    "# 7，9\n",
    "MX = 10**5+1\n",
    "MOD = 10**9+7\n",
    "f = [1, 1, 2, 4]\n",
    "g = [1, 1, 2, 4]\n",
    "for i in range(4,MX):  # 预处理所有长度的结果\n",
    "    f.append((f[i-1] + f[i-2] + f[i-3]) % MOD)\n",
    "    g.append((g[i-1] + g[i-2] + g[i-3] + g[i-4]) % MOD)\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        ans = 1\n",
    "        for ch,s in groupby(pressedKeys):\n",
    "            m = len(list(s))\n",
    "            ans = ans*g[m] if ch in '79' else ans*f[m]\n",
    "        return ans%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "f = [1, 1, 2, 4]\n",
    "g = [1, 1, 2, 4]\n",
    "for _ in range(10 ** 5 - 3):  # 预处理所有长度的结果\n",
    "    f.append((f[-1] + f[-2] + f[-3]) % MOD)\n",
    "    g.append((g[-1] + g[-2] + g[-3] + g[-4]) % MOD)\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        ans = 1\n",
    "        for ch, s in groupby(pressedKeys):\n",
    "            m = len(list(s))\n",
    "            ans = ans * (g[m] if ch in \"79\" else f[m]) % MOD\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\r\n",
    "# @lc app=leetcode.cn id=2266 lang=python3\r\n",
    "#\r\n",
    "# [2266] 统计打字方案数\r\n",
    "#\r\n",
    "\r\n",
    "MOD = 10 ** 9 + 7\r\n",
    "f = [1, 1, 2, 4]\r\n",
    "g = [1, 1, 2, 4]\r\n",
    "for _ in range(10 ** 5 - 3):  # 预处理所有长度的结果\r\n",
    "    f.append((f[-1] + f[-2] + f[-3]) % MOD)\r\n",
    "    g.append((g[-1] + g[-2] + g[-3] + g[-4]) % MOD)\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def countTexts(self, pressedKeys: str) -> int:\r\n",
    "        ans = 1\r\n",
    "        for ch, s in groupby(pressedKeys):\r\n",
    "            m = len(list(s))\r\n",
    "            ans = ans * (g[m] if ch in \"79\" else f[m]) % MOD\r\n",
    "        return ans\r\n",
    "\r\n",
    "\r\n",
    "    \r\n",
    "print(Solution().countTexts(\"22233\"))\r\n",
    "# @lc code=end\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理\n",
    "# '234568'\n",
    "mod = 10**9+7\n",
    "f = [1,1,2,4]\n",
    "# '79'\n",
    "g = [1,1,2,4]\n",
    "MX = 10**5+1\n",
    "for i in range(4,MX):\n",
    "    f.append((f[-1]+f[-2]+f[-3])%mod)\n",
    "    g.append((g[-1]+g[-2]+g[-3]+g[-4])%mod) \n",
    "# '79'\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        ans = 1\n",
    "        for ch,s in groupby(pressedKeys):\n",
    "            m = len(list(s))\n",
    "            if ch in '79':\n",
    "                ans *= g[m]\n",
    "            else:\n",
    "                ans *= f[m]\n",
    "        return ans%mod\n",
    "\n",
    "\n",
    "# # 2，3，4，5，6，8\n",
    "# # 7，9\n",
    "# MX = 10**5+1\n",
    "# MOD = 10**9+7\n",
    "# f = [1, 1, 2, 4]\n",
    "# g = [1, 1, 2, 4]\n",
    "# for i in range(4,MX):  # 预处理所有长度的结果\n",
    "#     f.append((f[i-1] + f[i-2] + f[i-3]) % MOD)\n",
    "#     g.append((g[i-1] + g[i-2] + g[i-3] + g[i-4]) % MOD)\n",
    "# class Solution:\n",
    "#     def countTexts(self, pressedKeys: str) -> int:\n",
    "#         ans = 1\n",
    "#         for ch,s in groupby(pressedKeys):\n",
    "#             m = len(list(s))\n",
    "#             ans = ans*g[m] if ch in '79' else ans*f[m]\n",
    "#         return ans%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        # m = 1e9+7\n",
    "        # # dp3 = [0, 1, 2, 4]\n",
    "        # # dp4 = [0, 1, 2, 4, 8]\n",
    "        # dp3 = [1, 1, 2, 4]\n",
    "        # dp4 = [1, 1, 2, 4]\n",
    "        # n = len(pressedKeys)\n",
    "        # for i in range(4, n+1):\n",
    "        #     dp3.append((dp3[i-1]+dp3[i-2]+dp3[i-3])%m)\n",
    "        #     dp4.append((dp4[i-1]+dp4[i-2]+dp4[i-3]+dp4[i-4])%m)\n",
    "        # cnt=1\n",
    "        # res=1\n",
    "        # for i in range(1, n):\n",
    "        #     if pressedKeys[i-1]==pressedKeys[i]:\n",
    "        #         cnt+=1\n",
    "        #     else:\n",
    "        #         if pressedKeys[i-1] in ['9', '7']:\n",
    "        #             res*=dp4[cnt]\n",
    "        #         else:\n",
    "        #             res*=dp3[cnt]\n",
    "        #         res%=m\n",
    "        #         cnt=1\n",
    "        # if pressedKeys[n-1] in ['9', '7']:\n",
    "        #     res*=dp4[cnt]\n",
    "        # else:\n",
    "        #     res*=dp3[cnt]\n",
    "        # res%=m\n",
    "        # return int(res)\n",
    "\n",
    "        m = 10 ** 9 + 7\n",
    "        dp3 = [1, 1, 2, 4]   # 连续按多次 3 个字母按键对应的方案数\n",
    "        dp4 = [1, 1, 2, 4]   # 连续按多次 4 个字母按键对应的方案数\n",
    "        n = len(pressedKeys)\n",
    "        for i in range(4, n + 1):\n",
    "            dp3.append((dp3[i-1] + dp3[i-2] + dp3[i-3]) % m)\n",
    "            dp4.append((dp4[i-1] + dp4[i-2] + dp4[i-3] + dp4[i-4]) % m)\n",
    "        res = 1   # 总方案数\n",
    "        cnt = 1   # 当前字符连续出现的次数\n",
    "        for i in range(1, n):\n",
    "            if pressedKeys[i] == pressedKeys[i-1]:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                # 对按键对应字符数量讨论并更新总方案数\n",
    "                if pressedKeys[i-1] in \"79\":\n",
    "                    res *= dp4[cnt]\n",
    "                else:\n",
    "                    res *= dp3[cnt]\n",
    "                res %= m\n",
    "                cnt = 1\n",
    "        # 更新最后一段连续字符子串对应的方案数\n",
    "        if pressedKeys[-1] in \"79\":\n",
    "            res *= dp4[cnt]\n",
    "        else:\n",
    "            res *= dp3[cnt]\n",
    "        res %= m\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "f=[0,1,2,4]\n",
    "g=[0,1,2,4,8]\n",
    "for _ in range(10**5-3):\n",
    "    f.append((f[-1]+f[-2]+f[-3])%MOD)\n",
    "    g.append((g[-1]+g[-2]+g[-3]+g[-4])%MOD)\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        ans = 1\n",
    "        for ch,s in groupby(pressedKeys):\n",
    "            m = len(list(s))\n",
    "            ans = ans* (g[m] if ch in \"79\" else f[m])%MOD\n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        n = len(pressedKeys)\n",
    "        mod = 10**9 + 7\n",
    "        dp3 = [1,1,2,4] + [0] * max(n-3, 0)\n",
    "        dp4 = [1,1,2,4] + [0] * max(n-3, 0)\n",
    "\n",
    "        for i in range(4,n+1):\n",
    "            dp3[i] = (dp3[i-1] + dp3[i-2] + dp3[i-3]) % mod\n",
    "            dp4[i] = (dp4[i-1] + dp4[i-2] + dp4[i-3] + dp4[i-4]) % mod\n",
    "\n",
    "        def map_cnt(c):\n",
    "            return 4 if c in \"79\" else 3\n",
    "\n",
    "        pressedKeys += \"#\"\n",
    "        cur = pressedKeys[0]\n",
    "        cnt = 1\n",
    "        ans = 1\n",
    "        for c in pressedKeys[1:]:\n",
    "            if cur == c:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                ans = (ans * (dp4[cnt] if cur in \"79\" else dp3[cnt])) % mod\n",
    "                cur = c \n",
    "                cnt = 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        m = 7+10 ** 9\n",
    "        # dp3 = [0, 1, 2, 4]\n",
    "        # dp4 = [0, 1, 2, 4, 8]\n",
    "        dp3 = [1, 1, 2, 4]\n",
    "        dp4 = [1, 1, 2, 4]\n",
    "        n = len(pressedKeys)\n",
    "        for i in range(4, n+1):\n",
    "            dp3.append((dp3[i-1]+dp3[i-2]+dp3[i-3])%m)\n",
    "            dp4.append((dp4[i-1]+dp4[i-2]+dp4[i-3]+dp4[i-4])%m)\n",
    "        cnt=1\n",
    "        res=1\n",
    "        for i in range(1, n):\n",
    "            if pressedKeys[i-1]==pressedKeys[i]:\n",
    "                cnt+=1\n",
    "            else:\n",
    "                if pressedKeys[i-1] in '79':\n",
    "                    res*=dp4[cnt]\n",
    "                else:\n",
    "                    res*=dp3[cnt]\n",
    "                res%=m\n",
    "                cnt=1\n",
    "        if pressedKeys[n-1] in '79':\n",
    "            res*=dp4[cnt]\n",
    "        else:\n",
    "            res*=dp3[cnt]\n",
    "        res%=m\n",
    "        return int(res)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        m = 10 ** 9 + 7\n",
    "        dp3 = [1, 1, 2, 4]   # 连续按多次 3 个字母按键对应的方案数\n",
    "        dp4 = [1, 1, 2, 4]   # 连续按多次 4 个字母按键对应的方案数\n",
    "        n = len(pressedKeys)\n",
    "        for i in range(4, n + 1):\n",
    "            dp3.append((dp3[i-1] + dp3[i-2] + dp3[i-3]) % m)\n",
    "            dp4.append((dp4[i-1] + dp4[i-2] + dp4[i-3] + dp4[i-4]) % m)\n",
    "        res = 1   # 总方案数\n",
    "        cnt = 1   # 当前字符连续出现的次数\n",
    "        for i in range(1, n):\n",
    "            if pressedKeys[i] == pressedKeys[i-1]:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                # 对按键对应字符数量讨论并更新总方案数\n",
    "                if pressedKeys[i-1] in \"79\":\n",
    "                    res *= dp4[cnt]\n",
    "                else:\n",
    "                    res *= dp3[cnt]\n",
    "                res %= m\n",
    "                cnt = 1\n",
    "        # 更新最后一段连续字符子串对应的方案数\n",
    "        if pressedKeys[-1] in \"79\":\n",
    "            res *= dp4[cnt]\n",
    "        else:\n",
    "            res *= dp3[cnt]\n",
    "        res %= m\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        m = 10 ** 9 + 7\n",
    "        dp3 = [1, 1, 2, 4]   # 连续按多次 3 个字母按键对应的方案数\n",
    "        dp4 = [1, 1, 2, 4]   # 连续按多次 4 个字母按键对应的方案数\n",
    "        n = len(pressedKeys)\n",
    "        for i in range(4, n + 1):\n",
    "            dp3.append((dp3[i-1] + dp3[i-2] + dp3[i-3]) % m)\n",
    "            dp4.append((dp4[i-1] + dp4[i-2] + dp4[i-3] + dp4[i-4]) % m)\n",
    "        res = 1   # 总方案数\n",
    "        cnt = 1   # 当前字符连续出现的次数\n",
    "        for i in range(1, n):\n",
    "            if pressedKeys[i] == pressedKeys[i-1]:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                # 对按键对应字符数量讨论并更新总方案数\n",
    "                if pressedKeys[i-1] in \"79\":\n",
    "                    res *= dp4[cnt]\n",
    "                else:\n",
    "                    res *= dp3[cnt]\n",
    "                res %= m\n",
    "                cnt = 1\n",
    "        # 更新最后一段连续字符子串对应的方案数\n",
    "        if pressedKeys[-1] in \"79\":\n",
    "            res *= dp4[cnt]\n",
    "        else:\n",
    "            res *= dp3[cnt]\n",
    "        res %= m\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        n = len(pressedKeys)\n",
    "        mod = 10**9 + 7\n",
    "        dp3 = [1,1,2,4] + [0] * max(n-3, 0)\n",
    "        dp4 = [1,1,2,4] + [0] * max(n-3, 0)\n",
    "\n",
    "        for i in range(4,n+1):\n",
    "            dp3[i] = (dp3[i-1] + dp3[i-2] + dp3[i-3]) % mod\n",
    "            dp4[i] = (dp4[i-1] + dp4[i-2] + dp4[i-3] + dp4[i-4]) % mod\n",
    "\n",
    "        def map_cnt(c):\n",
    "            return 4 if c in \"79\" else 3\n",
    "\n",
    "        pressedKeys += \"#\"\n",
    "        cur = pressedKeys[0]\n",
    "        cnt = 1\n",
    "        ans = 1\n",
    "        for c in pressedKeys[1:]:\n",
    "            if cur == c:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                ans = (ans * (dp4[cnt] if cur in \"79\" else dp3[cnt])) % mod\n",
    "                cur = c \n",
    "                cnt = 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        mod = int(1e9 + 7)\n",
    "\n",
    "        alph = {\n",
    "            2:3,\n",
    "            3:3,\n",
    "            4:3,\n",
    "            5:3,\n",
    "            6:3,\n",
    "            7:4,\n",
    "            8:3,\n",
    "            9:4\n",
    "        }\n",
    "\n",
    "        # 3个头\n",
    "        f = [1, 1, 2, 4]\n",
    "\n",
    "        # 4个头\n",
    "        g = [1, 1, 2, 4]\n",
    "\n",
    "        for i in range(4, int(1e5) + 1):\n",
    "            f.append((f[-1] + f[-2] + f[-3]) % mod)\n",
    "            g.append((g[-1] + g[-2] + g[-3] + g[-4]) % mod)\n",
    "\n",
    "\n",
    "        res = 1\n",
    "\n",
    "        i = 0\n",
    "        while i < len(pressedKeys):\n",
    "            start = i\n",
    "\n",
    "            while i < len(pressedKeys) and pressedKeys[i] == pressedKeys[start]:\n",
    "                i += 1\n",
    "            \n",
    "            size = i - start\n",
    "\n",
    "            # res *= dp(alph[int(pressedKeys[start])], size)\n",
    "            res *= f[size] if alph[int(pressedKeys[start])] == 3 else g[size]\n",
    "            res %= mod\n",
    "        \n",
    "\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, s: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(s)\n",
    "\n",
    "        f3 = [1, 1, 2, 4]\n",
    "        f4 = [1, 1, 2, 4]\n",
    "\n",
    "        for i in range(4, n+1):\n",
    "            f3.append((f3[i-1] + f3[i-2] + f3[i-3]) % mod)\n",
    "            f4.append((f4[i-1] + f4[i-2] + f4[i-3] + f4[i-4]) % mod)\n",
    "\n",
    "        cnt = 1\n",
    "        ans = 1\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if s[i] == s[i-1]:\n",
    "                cnt += 1\n",
    "            # 处理前一段\n",
    "            else:\n",
    "                if s[i-1] in '79':\n",
    "                    ans = ans * f4[cnt] % mod\n",
    "                else:\n",
    "                    ans = ans * f3[cnt] % mod\n",
    "                cnt = 1\n",
    "\n",
    "        # 处理最后一段\n",
    "        if s[-1] in '79':\n",
    "            ans = ans * f4[cnt] % mod\n",
    "        else:\n",
    "            ans = ans * f3[cnt] % mod\n",
    "        \n",
    "        return ans\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, s: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        f3 = [1, 1, 2, 4]\n",
    "        f4 = [1, 1, 2, 4]\n",
    "        n = len(s)\n",
    "\n",
    "        for i in range(4, n+1):\n",
    "            f3.append((f3[i-1] + f3[i-2] + f3[i-3]) % mod)\n",
    "            f4.append((f4[i-1] + f4[i-2] + f4[i-3] + f4[i-4]) % mod)\n",
    "        \n",
    "        ans = 1\n",
    "        for ch, cs in groupby(s):\n",
    "            sz = len(list(cs))\n",
    "            if ch in '79':\n",
    "                ans = ans * f4[sz] % mod\n",
    "            else:\n",
    "                ans = ans * f3[sz] % mod\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "from collections import Counter\r\n",
    "class Solution:\r\n",
    "    def countTexts(self, pressedKeys: str) -> int:\r\n",
    "        MOD = 10 ** 9 + 7\r\n",
    "        f = [1, 1, 2, 4]\r\n",
    "        g = [1, 1, 2, 4]\r\n",
    "        for _ in range(10 ** 5 - 3):  # 预处理所有长度的结果\r\n",
    "            f.append((f[-1] + f[-2] + f[-3]) % MOD)\r\n",
    "            g.append((g[-1] + g[-2] + g[-3] + g[-4]) % MOD)\r\n",
    "\r\n",
    "        ans = 1\r\n",
    "        h = lambda k, v: f[v] if k not in '79' else g[v]\r\n",
    "        for ch, s in groupby(pressedKeys):\r\n",
    "            m = len(list(s))\r\n",
    "            ans = (ans*h(ch, m)) % (10**9+7)\r\n",
    "        return ans \r\n",
    "    \r\n",
    "print(Solution().countTexts(\"22233\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "md = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        n = len(pressedKeys)\n",
    "        dp3 = [1, 1, 2, 4]   # 连续按多次 3 个字母按键对应的方案数\n",
    "        dp4 = [1, 1, 2, 4]   # 连续按多次 4 个字母按键对应的方案数\n",
    "        n = len(pressedKeys)\n",
    "        for i in range(4, n + 1):\n",
    "            dp3.append((dp3[i-1] + dp3[i-2] + dp3[i-3]) % md)\n",
    "            dp4.append((dp4[i-1] + dp4[i-2] + dp4[i-3] + dp4[i-4]) % md)\n",
    "\n",
    "        res = 1\n",
    "        cnt = 1\n",
    "        for i in range(1, n):\n",
    "            if pressedKeys[i] == pressedKeys[i-1]:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                if pressedKeys[i-1] in \"79\":\n",
    "                    res *= dp4[cnt]\n",
    "                else:\n",
    "                    res *= dp3[cnt]\n",
    "                res %= md\n",
    "                cnt = 1\n",
    "\n",
    "        if pressedKeys[-1] in \"79\":\n",
    "            res *= dp4[cnt]\n",
    "        else:\n",
    "            res *= dp3[cnt]\n",
    "        res %= md\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        m = 10 ** 9 + 7\n",
    "        n = len(pressedKeys)\n",
    "        dp3 = [0, 1, 2, 4, 7]\n",
    "        dp4 = [0, 1, 2, 4, 8]\n",
    "        if n > 4:\n",
    "            for i in range(5, n+1):\n",
    "                dp3.append((dp3[i-1] + dp3[i-2] + dp3[i-3]) % m)\n",
    "                dp4.append((dp4[i-1] + dp4[i-2] + dp4[i-3] + dp4[i-4]) % m)\n",
    "        if len(pressedKeys) == 0:\n",
    "            return 0\n",
    "        ans = 1\n",
    "        i, j = 0, 1\n",
    "        while i < n:\n",
    "            for j in range(i+1, n+1):\n",
    "                if (j < n and pressedKeys[j] != pressedKeys[i]) or j == n:\n",
    "                    if pressedKeys[i] == '7' or pressedKeys[i] == '9':\n",
    "                        ans *= dp4[j-i]\n",
    "                    else:\n",
    "                        ans *= dp3[j-i]\n",
    "                    ans = ans % (10**9 + 7)\n",
    "                    i = j\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "from collections import Counter\r\n",
    "class Solution:\r\n",
    "    def countTexts(self, pressedKeys: str) -> int:\r\n",
    "        MOD = 10 ** 9 + 7\r\n",
    "        f = [1, 1, 2, 4]\r\n",
    "        g = [1, 1, 2, 4]\r\n",
    "        for _ in range(10 ** 5 - 3):  # 预处理所有长度的结果\r\n",
    "            f.append((f[-1] + f[-2] + f[-3]) % MOD)\r\n",
    "            g.append((g[-1] + g[-2] + g[-3] + g[-4]) % MOD)\r\n",
    "\r\n",
    "        ans = 1\r\n",
    "        h = lambda k, v: f[v] if k not in '79' else g[v]\r\n",
    "        for ch, s in groupby(pressedKeys):\r\n",
    "            m = len(list(s))\r\n",
    "            ans = (ans*h(ch, m)) % (10**9+7)\r\n",
    "        return ans \r\n",
    "    \r\n",
    "print(Solution().countTexts(\"22233\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        n = len(pressedKeys)\n",
    "        mod = 10**9 + 7\n",
    "        dp3 = [1,1,2,4] + [0] * max(n-3, 0)\n",
    "        dp4 = [1,1,2,4] + [0] * max(n-3, 0)\n",
    "\n",
    "        for i in range(4,n+1):\n",
    "            dp3[i] = (dp3[i-1] + dp3[i-2] + dp3[i-3]) % mod\n",
    "            dp4[i] = (dp4[i-1] + dp4[i-2] + dp4[i-3] + dp4[i-4]) % mod\n",
    "\n",
    "        def map_cnt(c):\n",
    "            return 4 if c in \"79\" else 3\n",
    "\n",
    "        ans = 1\n",
    "        for c, s in itertools.groupby(pressedKeys):\n",
    "            cnt = len(list(s))\n",
    "            ans = (ans * (dp4[cnt] if c in \"79\" else dp3[cnt])) % mod\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        res = 1\n",
    "        left = 0\n",
    "        @cache\n",
    "        def calc3(L):\n",
    "            if L == 1:\n",
    "                return 1\n",
    "            elif L == 2:\n",
    "                return 2\n",
    "            elif L == 3:\n",
    "                return 4\n",
    "            else:\n",
    "                return (calc3(L-1) + calc3(L-2) + calc3(L-3)) % MOD\n",
    "        @cache\n",
    "        def calc4(L):\n",
    "            if L == 1:\n",
    "                return 1\n",
    "            elif L == 2:\n",
    "                return 2\n",
    "            elif L == 3:\n",
    "                return 4\n",
    "            elif L == 4:\n",
    "                return 8\n",
    "            else:\n",
    "                return (calc4(L-1) + calc4(L-2) + calc4(L-3) + calc4(L-4)) % MOD\n",
    "\n",
    "        for right in range(len(pressedKeys)):\n",
    "            if pressedKeys[right] == pressedKeys[left]:\n",
    "                continue\n",
    "            # print(left, right)\n",
    "            # print(calc3(right - left))\n",
    "            if pressedKeys[left] in ['7', '9']:\n",
    "                res = (res * calc4(right - left)) % MOD\n",
    "            else:\n",
    "                res = (res * calc3(right - left)) % MOD\n",
    "            left = right\n",
    "        # print(left, right)\n",
    "        # print(calc3(right - left))\n",
    "        right += 1\n",
    "        if pressedKeys[left] in ['7', '9']:\n",
    "            res = (res * calc4(right - left)) % MOD\n",
    "        else:\n",
    "            res = (res * calc3(right - left)) % MOD\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        n = len(pressedKeys)\n",
    "        four = ('7', '9')\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(idx):\n",
    "            if idx == n:\n",
    "                return 1\n",
    "            res = 0\n",
    "            r = min(n, idx + (4 if pressedKeys[idx] in four else 3))\n",
    "            for i in range(idx, r):\n",
    "                if pressedKeys[i] != pressedKeys[idx]:\n",
    "                    break\n",
    "                res += dfs(i + 1)\n",
    "                res %= kmod\n",
    "            return res\n",
    "\n",
    "        ans = dfs(0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        @cache\n",
    "        def cal(x: int, nine_seven: bool) -> int:\n",
    "            if x <= 2:\n",
    "                return x\n",
    "            if x == 3:\n",
    "                return 4\n",
    "            if nine_seven and x == 4:\n",
    "                return 8\n",
    "            if nine_seven:\n",
    "                return (cal(x - 1, nine_seven) + cal(x - 2, nine_seven) + cal(x - 3, nine_seven) + cal(x - 4, nine_seven)) % MOD\n",
    "            return (cal(x - 1, nine_seven) + cal(x - 2, nine_seven) + cal(x - 3, nine_seven)) % MOD\n",
    "\n",
    "        ans = 1\n",
    "        for ch, v in itertools.groupby(pressedKeys):\n",
    "            ans = ans * cal(len(list(v)), ch == '9' or ch == '7') % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        @cache\n",
    "        def check(c, n):\n",
    "            if n < 0:\n",
    "                return 0\n",
    "            if n == 0:\n",
    "                return 1\n",
    "            if c =='7' or c == '9':\n",
    "                return (check(c, n-1) + check(c, n-2)+check(c, n-3) + check(c, n-4)) % mod\n",
    "            else:\n",
    "                return (check(c, n-1) + check(c, n-2)+check(c, n-3)) % mod\n",
    "        \n",
    "        ans = 1\n",
    "        pre = 0\n",
    "        for i in range(1, len(pressedKeys)):\n",
    "            if pressedKeys[i] != pressedKeys[i-1]:\n",
    "                ans *= check(pressedKeys[i-1], i - pre)\n",
    "                ans %= mod\n",
    "                pre = i\n",
    "        ans *= check(pressedKeys[len(pressedKeys) - 1], len(pressedKeys) - pre)\n",
    "        ans %= mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        n=len(pressedKeys)\n",
    "\n",
    "        ll=[0,0,3,3,3,3,3,4,3,4]\n",
    "        mod=10**9+7\n",
    "        @cache\n",
    "        def dfs(l,can):\n",
    "            if l==0:\n",
    "                return 1\n",
    "            ans=0\n",
    "            for i in range(1,min(can+1,l+1)):\n",
    "                ans+=dfs(l-i,can)\n",
    "\n",
    "\n",
    "            return ans%mod\n",
    "\n",
    "\n",
    "        ans=1\n",
    "        pre=1\n",
    "        for i in range(1,n):\n",
    "            if pressedKeys[i]!=pressedKeys[i-1]:\n",
    "                ans*=dfs(pre,ll[int(pressedKeys[i-1])])\n",
    "                ans=ans%mod\n",
    "                pre=1\n",
    "            else:\n",
    "                pre+=1\n",
    "        ans*=dfs(pre,ll[int(pressedKeys[-1])])\n",
    "\n",
    "\n",
    "        return ans%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "       @cache\n",
    "       def dfs(i: int) -> int:\n",
    "          if i == n:\n",
    "             return 1\n",
    "          res = 0\n",
    "          cnt = mp[int(pressedKeys[i])]\n",
    "          j = i\n",
    "          while j < n and pressedKeys[i] == pressedKeys[j] and j - i + 1 <= cnt:\n",
    "             res += dfs(j + 1)\n",
    "             res %= MOD\n",
    "             j += 1\n",
    "          return res\n",
    "       MOD = 10 ** 9 + 7\n",
    "       n = len(pressedKeys)\n",
    "       mp = [3] * 10\n",
    "       mp[7] = 4\n",
    "       mp[9] = 4\n",
    "       return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countTexts(self, s: str) -> int:\r\n",
    "        mod = 10 ** 9 + 7\r\n",
    "        n = len(s)\r\n",
    "        mp = {}\r\n",
    "        for x in \"234568\":\r\n",
    "            mp[x] = 3 \r\n",
    "        \r\n",
    "        @cache\r\n",
    "        def dfs(i:int) -> int:\r\n",
    "            if i == n:\r\n",
    "                return 1 \r\n",
    "            res = 0\r\n",
    "            mx = mp[s[i]] if s[i] in mp else 4\r\n",
    "            j = i \r\n",
    "            while j < len(s) and s[j] == s[i] and j - i + 1 <= mx:\r\n",
    "                res = (res +  dfs(j + 1)) % mod \r\n",
    "                j += 1\r\n",
    "            return res \r\n",
    "        return dfs(0)\r\n",
    "            \r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, s: str) -> int:\n",
    "        @cache\n",
    "        def f(i):\n",
    "            if i >= len(s):\n",
    "                return 1\n",
    "            ans = 0\n",
    "            if s[i] in '79':\n",
    "                for k in range(1, 5):\n",
    "                    if s[i:i+k] == s[i] * k:\n",
    "                        ans += f(i+k)\n",
    "            else:\n",
    "                for k in range(1, 4):\n",
    "                    if s[i:i+k] == s[i] * k:\n",
    "                        ans += f(i+k)\n",
    "            return ans % (10**9+7)\n",
    "        \n",
    "        return f(0) % (10**9+7)\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        n = len(pressedKeys)\n",
    "        Mod = int(1e9+7)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == 0:\n",
    "                return 1\n",
    "            x = pressedKeys[i-1]\n",
    "            if x in '234568':\n",
    "                l = 3 \n",
    "            else:\n",
    "                l = 4\n",
    "            tot = 0  \n",
    "            for j in range(i-1, max(i-l, 0) - 1,-1):\n",
    "                tot += dfs(j) \n",
    "                tot %= Mod \n",
    "                if j > 0 and pressedKeys[j-1] != x:\n",
    "                    break \n",
    "            #print(i, tot) \n",
    "            return tot \n",
    "        ans = dfs(n)\n",
    "        return ans \n",
    "                \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        # n = len(pressedKeys)\n",
    "        mod = 10**9 + 7\n",
    "\n",
    "        @cache\n",
    "        def dp(k, cnt):\n",
    "            if cnt <= 1:\n",
    "                return 1\n",
    "\n",
    "            return sum(dp(k, cnt-i) for i in range(1, min(cnt,k)+1)) % mod\n",
    "\n",
    "        ans = 1\n",
    "        for c, s in itertools.groupby(pressedKeys):\n",
    "            cnt = len(list(s))\n",
    "            ans = (ans * (dp(4, cnt) if c in \"79\" else dp(3, cnt))) % mod\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        digit_to_map = {\"2\":3,\"3\":3, \"4\":3,\"5\":3,\"6\":3,\"7\":4,\"8\":3,\"9\":4}\n",
    "        three =[]\n",
    "        four = []\n",
    "        key_len = len(pressedKeys)\n",
    "        left = right = 0\n",
    "        three_max = 0\n",
    "        four_max = 0\n",
    "        while right< key_len:\n",
    "            if pressedKeys[right]!= pressedKeys[left]:\n",
    "                v = pressedKeys[left]\n",
    "                dis = right-left\n",
    "                if digit_to_map[v] ==3:\n",
    "                    three.append(dis)\n",
    "                    if dis>three_max:\n",
    "                        three_max = dis\n",
    "                else:\n",
    "                    four.append(dis)\n",
    "                    if dis>four_max:\n",
    "                        four_max= dis\n",
    "                left = right\n",
    "            right+=1\n",
    "        if left != key_len-1:\n",
    "            v = pressedKeys[left]\n",
    "            dis = right-left\n",
    "            if digit_to_map[v] ==3:\n",
    "                three.append(dis)\n",
    "                if dis>three_max:\n",
    "                    three_max = dis\n",
    "            else:\n",
    "                four.append(dis)\n",
    "                if dis>four_max:\n",
    "                    four_max= dis\n",
    "    \n",
    "        dp3 = [1]*max(three_max,4)\n",
    "        dp4 = [1]*max(four_max,4)\n",
    "        for i in range(1, 3):\n",
    "            dp3[i] = dp3[i-1]*2\n",
    "            dp4[i] = dp4[i-1]*2\n",
    "        dp4[3] = 8\n",
    "        dp3_old = 7\n",
    "        dp4_old = 15\n",
    "        for i in range(3, three_max):\n",
    "            dp3[i] = dp3_old\n",
    "            dp3_old =2*dp3_old-dp3[i-3]\n",
    "            \n",
    "        for i in range(4, four_max):\n",
    "            dp4[i] = dp4_old\n",
    "            dp4_old = 2*dp4_old-dp4[i-4]\n",
    "            \n",
    "        # print(dp3)\n",
    "        # print(three_max)\n",
    "\n",
    "        ans = 1\n",
    "        for v in three:\n",
    "            ans *= dp3[v-1]\n",
    "        for v in four:\n",
    "            ans *= dp4[v-1]\n",
    "        return ans %(10**9+7)\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, pressedKeys: str) -> int:\n",
    "        def find(count,i):\n",
    "            dp=[1]*count\n",
    "            if i =='9' or i=='7':\n",
    "                maximum=4\n",
    "            else:\n",
    "                maximum=3\n",
    "            for i in range(min(maximum,count)):\n",
    "                dp[i]= 1<<i\n",
    "            for i in range(maximum,count):\n",
    "                c=0\n",
    "                for j in range(maximum):\n",
    "                    c+=dp[i-j-1]\n",
    "                dp[i]=c\n",
    "            return dp[-1]%(10**9 + 7)\n",
    " \n",
    "        last=None\n",
    "        count=1\n",
    "        flag=1\n",
    "        pressedKeys+='0'\n",
    "        for i in pressedKeys:\n",
    "            if i==last:\n",
    "                count+=1\n",
    "            else:\n",
    "                flag=flag*find(count,last)%(10**9 + 7)\n",
    "                count=1\n",
    "                last=i\n",
    "        return flag\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTexts(self, ps: str) -> int:\n",
    "        d = [0]*(len(ps)+1)\n",
    "        d[0]=1\n",
    "        M= 10**9+7\n",
    "        for i, c in enumerate(ps):\n",
    "            a = d[i]\n",
    "            w  = 3\n",
    "            if c in '79':\n",
    "                w+=1\n",
    "            for j in range(1,w):\n",
    "                if i-j < 0 or c!=ps[i-j]:\n",
    "                    break;\n",
    "                \n",
    "                a += d[i-j]\n",
    "            d[i+1]+=a\n",
    "            # print(d[i+1])\n",
    "        return d[-1]%M\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
